package com.zp.self.module.level_4_算法练习.算法.动态规划;

import java.util.Arrays;

/**
 * @author By ZengPeng
 */
public class 力扣_673_最长递增子序列的个数 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_673_最长递增子序列的个数().findNumberOfLIS(new int[]{1,3,5,4,7}));//2
        System.out.println(new 力扣_673_最长递增子序列的个数().findNumberOfLIS(new int[]{2,2,2,2,2}));//5
        System.out.println(new 力扣_673_最长递增子序列的个数().findNumberOfLIS(new int[]{1,5,3,6,5,5,5,5,8,9}));//6
        System.out.println(new 力扣_673_最长递增子序列的个数().findNumberOfLIS(new int[]{1,2,4,3,5,4,7,2}));//3
        System.out.println(new 力扣_673_最长递增子序列的个数().findNumberOfLIS(new int[]{7,2,2312,222,2,1}));//4
    }

    /**
    题目：给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
     注意 这个数列必须是 严格 递增的。

     示例 1:
     输入: [1,3,5,4,7]
     输出: 2
     解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

     示例 2:
     输入: [2,2,2,2,2]
     输出: 5
     解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

    分析：【PR 💜💜💜💜💜💜】
       1.常规动态规划+递归：求出从index开始，每个节点的最大长度，统计最大值，再次遍历最大值个数
                    --废弃，只能找打每个节点的最优解，还得再递归每个最优解方案

       2.动态规划+迭代+二分法+位图：我们定义tails[k]为:子序列长度为：k+1时，最小的那个值
                             在遍历计算每个 tails[k]，不断更新长度为 [1,k] 的子序列尾部元素值，始终保持每个尾部元素值最小,
                             只要你大于这个最小值，说明你的长度就大于了k+1，可以通过二分法找到第一个小于tails[k]的值，其实就是要插入的位置
                             例如 [1,5,3]]：
                             遍历到元素 5时，长度为 2的子序列尾部元素值为 5；tails= [1,5]
                             当遍历到元素 3 时，尾部元素值应更新至 3，因为 3 遇到比它大的数字的几率更大）。tails= [1,3]
                    --废弃，情况太多，不太好用位图分析统计
       3.动态规划+迭代：每到一个新的节点，需要判断与前面节点的大小，如果大于前面的节点，那么当前比较当前dp[i],dp[pro]+1的大小，得到最大长度
                        int[] dpCount 记录能达到每个下标方式的总数：【每次只用将前面的一步的方式累加即可】
                    --执行用时：15 ms, 在所有 Java 提交中击败了92.97%的用户

    边界值 & 注意点：
       1.
     **/
    public int findNumberOfLIS(int[] nums) {
        // 3.动态规划+迭代：
        int len = nums.length;
        int[] dp = new int[len];
        int[] dpCount = new int[len]; //记录能达到每个下标方式的总数
        int max=0;
        for (int i = 0; i < len; i++) {
            int count=0;
            for (int pro = 0; pro < i; pro++) {
                if(nums[pro]<nums[i]){
                    if(dp[pro]+1>dp[i]){
                        dp[i] =dp[pro]+1;
                        count=dpCount[pro];//【每次只用将前面的一步的方式累加即可】
                    }else if(dp[pro]+1 == dp[i]){//【每次只用将前面的一步的方式累加即可】
                        count+=dpCount[pro];
                    }
                }
            }
            if(dp[i]==0)
                dpCount[i]=1;
            else
                dpCount[i]=count;
            max=Math.max(max,dp[i]);
        }
        int res= 0;
        for (int i = 0; i < dpCount.length; i++) {
            if(dp[i]==max)
                res+=dpCount[i];
        }
        return res;
    }
        // 1.动态规划+递归：
        /*int[] dp = new int[nums.length];
        int max =1;
        for (int i = 0; i < dp.length; i++) {
            dfs(i, nums, dp);//找到以index下标为起点的最长子序列
            max = Math.max(max,dp[i]);//遍历dp每个节点的最长序列，返回最大值 。
        }
        int count =0;
        for (int i : dp) {
           if(i==max)count++;
        }
        return count;
    }

    //递归三部曲：单步操作，终止条件，返回值 {10,9,2,5,3,7,101,18}
    *//**
     * Description: 明确这个递归的作用：找到以index下标为起点的最长子序列
     * @return int
     *//*
    private int dfs(int index, int[] nums, int[] dp) {
        if(dp[index]!=0) return dp[index];
        int max=0;
        for (int i = index+1; i < nums.length; i++) {//这里可以提前结束，不用遍历后面每个值
            if(nums[i]>nums[index])
                max = Math.max(max,dfs(i,nums,dp));//---优化：即使不是最大，也应该要记录其长度嘛
        }
        dp[index]=max+1;
        return dp[index];
    }*/
    // 2.动态规划+迭代+二分法+位图：我们定义tails[k]为:子序列长度为：k+1时，最小的那个值
        /*int len = nums.length,index=0;//index 表示tails 中有多少种长度情况，二分查找只需要找这个[0,index]范围
        int[] tails = new int[len];
        int[] count = new int[len];//用于位图记录每个长度的数量
        tails[0]=nums[0];
        count[0]++;
        for (int i = 1; i <len; i++) {
          int newIndex = search(tails,index,nums[i]);
          if(newIndex>index)
              index = newIndex;
            if(newIndex==index)
            count[newIndex]++;
            tails[newIndex] =nums[i];
        }
        int  res =1;
        for (int i = 0; i <= index; i++) {
            res+= (count[i]-1);
        }
        return res;
    }*/

    private int search(int[] tails, int right, int num) {
        int left = 0;
        while (left<=right){
            int mid =left+(right-left)/2;
            if(num>tails[mid])
                left=mid+1;
            else if(num<tails[mid])
                right=mid-1;
            else
                return mid;
        }
        return right+1;
    }
}
